# -*- coding: utf-8 -*-
# @Author: shj
# @Date: 2020-04-10 11:34:49
# @LastEditTime: 2020-04-10 19:17:51
# @LastEditors: shj
# @Description: 贪婪法解决背包问题(性价比最高的物品优先)
# @FilePath: /python3/algorithms/greedy_backpake.py
"""
贪婪法 - 在对问题求解时，总是做出在当前看来最好的选择，
不追求最优解，快速找到满意解。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，
但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

输入下方所有内容：
20 6
电脑 200 20
收音机 20 4
钟 175 10
花瓶 50 2
书 10 1
油画 90 9
"""


class Things(object):
    '''物品'''
    def __init__(self, name, value, weight):
        '''初始化
        :param name: 物品名
        :param value: 价值
        :param weight: 重量
        '''
        self._name = name
        self._value = value
        self._weight = weight

    @property
    def weight_value(self):
        '''计算性价比'''
        return self._weight / self._value


def input_thing():
    '''输入物品信息
    :param name_str: 物品名
    :param value_str: 物品价值
    :param weight_str: 物品重量
    '''
    name_str, value_str, weight_str = input().split()
    return name_str, int(value_str), int(weight_str)


def main():
    '''主函数
    :param pack_capacity: 背包容量
    :param things_number: 物品数目（不是背包可装的数目，而是房间中物品的数量）
    :param all_things: 物品信息
    :param total_weight: 背包中的物品总重量
    :param total_value: 背包中的物品总价值
    '''
    pack_capacity, things_number = map(int, input('请输入背包容量和物品数目:\n').split())
    all_things = []
    print('请输入物品信息:')
    for _ in range(things_number):
        # 添加物品信息
        all_things.append(Things(*input_thing()))
    # 对输出的物品进行计算性价比
    all_things.sort(key=lambda x: x.weight_value)
    total_weight = 0  # 背包中的物品总重量
    total_value = 0  # 背包中的物品总价值
    print('*' * 20)
    for thing in all_things:
        if total_weight + thing._weight < pack_capacity:
            print(f'<{thing._name}>被放入背包')
            total_weight += thing._weight
            total_value += thing._value

    print(f'背包中物品的总重量为：{total_weight}, 总价值为：{total_value}')


if __name__ == "__main__":
    main()